1. Field of the Invention
Example embodiments of the present invention relate in general to a cryptographic system and method for encrypting input data.
2. Description of the Related Art
In an effort to solve some of the problems in modern confidential data communications systems, hardware cryptographic systems based on well-known crypto-algorithms have become popular in an effort to satisfy continually growing performance requirements. These crypto-algorithms include public key algorithms, for example, Rivest-Shamir-Adleman (RSA) and Elliptic Curve Cryptography (ECC), and symmetric key algorithms, for example, the Data Encryption Standard (DES) and the Advanced Encryption Standard (AES).
Public Key Infrastructure (PKI) satisfying a high security level is widely used in data processing systems. Moreover, highly secure signature protocols can be implemented with only a PKI-based cryptosystem. This is one reason why interest in PKI has been growing in recent times.
But the efficient implementation of PKI requires the usage of a hardware realization of one or more specialized co-processors, also known as a “crypto-engine.” For several decades, and in addition to hardware-oriented crypto-systems, new crypto-analysis methods, for example, Side-Channel Analysis (SCA) have been developed. There are several different attack methodologies, including Timing Analysis, Power Analysis, Electro-Magnetic Analysis, and Different Faults Analysis (DFA). It is known that these types of attack techniques can successfully attack the crypto-systems and obtain secret keys in less time and with less effort.
Accordingly, the development of countermeasures for use against these cryptanalysis methods (such as SCA) is becoming an important task for the future. In the DPA attack, which is a type of SCA, power tracks during scalar multiplication operations are analyzed to obtain information on secret keys. DPA attacks are based on a hypothesis that power tracks are correlated to instructions that a cryptographic device is executing, as well as to values of operands in the cryptographic process. Thus, examination of the power tracks can reveal information about the instructions being executed and the contents of data registers. In the case that the cryptographic device is executing a secret-key cryptographic operation, it may then be possible to deduce the secret key.
In Simple Power Analysis (SPA) attacks, information about secret keys can be deduced directly by examining the power tracks from a single secret key operation. Implementations of elliptic curve (EC) point multiplication algorithms may be particularly vulnerable, because the usual formulas for adding and doubling points are quite different and therefore may have power tracks which can be distinguished. Any implementation where the execution path is determined by secret key bits has potential vulnerability.
DPA attacks exploit variations in power consumption that are correlated to the data values being manipulated. These variations are typically much smaller than those associated with different instruction sequences, and may be obfuscated by noise and measurement errors. Statistical methods are used on a collection of power tracks in order to reduce the noise and strengthen the differential analysis.
To counter the SPA attacks, there are number of different countermeasures. However, most of the SPA countermeasures are weak as against DPA attacks. A DPA attack is more complex relative to an SPA attack and requires analysis of a substantial number of power tracks, yet is still applicable to leaking secret information. The complexity of the DPA attack can be measured in terms of a requested number of power tracks and in terms of the calculations performed by hardware resources. Of the many DPA countermeasure techniques have been developed, one of more popular techniques is a secret key exponent blinding countermeasure.
The PKI has many different algorithms for realizing encryption: hashing, signature generation and verification features. One of the main operations for these features is a modular exponentiation operation for an RSA-like system and a scalar multiplication operation for an ECC system.
These operations have substantially complex computation processes. Thus, to speed up the operations, many different methods have been used, for example, “Binary LTR/RTL,” “Beta-ry LTR/RTL,” and “Window LTR/RTL.” Herein, LTR means left-to-right processing, and RTL means right-to-left processing.
FIG. 1 is an illustration for explaining conventional multiple scalar multiplication. Referring to FIG. 1, resultant data R=kP+lQ for secret keys k and l is obtained by accumulating d times using a formula R=2WR+(KiP+LiQ) by referring to a relevant lookup table value for a 2×w window while shifting the secret keys k and l every w bits in the right direction. Herein, each of P and Q can be input data or a set of input data and basic data. This method is known as Shamir's trick and can be used for a secret-key exponent blinding countermeasure. In each multiplication step, w doubling operations and a single adding operation are performed. However, for such a lookup table, the number of data to be referred to is 22w−1, e.g., 0P+1Q, 1P+0Q, 0P+2Q, . . . , (2w−1)P+(2w−1)Q, thereby requiring substantial memory capacity to store all the data.
In a practical secret-key exponent blinding countermeasure, a resultant point Q=kP is obtained by splitting the secret key k into two parts, e.g., k=k1+k2, performing two scalar multiplication operations Q1=k1P and Q2=k2P, and then performing a final adding operation Q=Q1+Q2.
FIGS. 2A and 2B are illustrations for explaining conventional system performance when ECC is performed by splitting a secret key into two pairs. In a typical binary algorithm in which Q=kP is directly implemented, the number of operations O(n), for the scalar multiplication operation is given as O(n)=n·DBL+(0.2 . . . 0.5)n·ADD, wherein DBL denotes an EC doubling operation, ADD denotes an EC adding operation, and n=log2 k (the number of bits of a binary representation secret key). However, as compared to the typical binary algorithm, the method of splitting the secret key into two parts requires almost double the number of operations since O(n)≅2([log2 k2]·DBL+(0.2 . . . 0.5)[log2 k2]·ADD)+ADD when the number of bits of k2 is almost the same as the number of bits of k as illustrated in FIG. 2A. When the number of bits of k2 is substantially less than the number of bits of k as illustrated in FIG. 2B, then O(n)≅[log2 k1]·DBL+(0.2 . . . 0.5)[log2 k1]·ADD+[log2 k2]·DBL+(0.2 . . . 0.5)[log2 k2]·ADD+ADD. Performance deterioration is acceptable in this case, but security is poor due to a change of only a portion of lower bits of k. In this case, the method of splitting the secret key into two parts has such complexity that an attacker can realize the changed lower bits of k by performing an exhausted computation for upper bits [log2k]−[log2k2] and the remaining lower bits related to k2 among the secret key.